package com.sheng.leetcode.year2023.month04.day10;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2023/04/10
 * <p>
 * 1019. 链表中的下一个更大节点<p>
 * <p>
 * 给定一个长度为 n 的链表 head<p>
 * 对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，<p>
 * 对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。<p>
 * 返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。<p>
 * 如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：head = [2,1,5]<p>
 * 输出：[5,5,0]<p>
 * <p>
 * 示例 2：<p>
 * 输入：head = [2,7,4,3,5]<p>
 * 输出：[7,0,5,5,0]<p>
 * <p>
 * 提示：<p>
 * 链表中节点数为 n<p>
 * 1 <= n <= 10^4<p>
 * 1 <= Node.val <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/next-greater-node-in-linked-list">1019. 链表中的下一个更大节点</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1019 {

    @Test
    public void test01() {
//        ListNode head = new ListNode(2, new ListNode(1, new ListNode(5)));
        ListNode head = new ListNode(2, new ListNode(7, new ListNode(4, new ListNode(3, new ListNode(5)))));
        System.out.println(Arrays.toString(new Solution().nextLargerNodes(head)));
    }
}

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();
        for (; head != null; head = head.next) {
            list.add(head.val);
        }
        int size = list.size();
        int[] ans = new int[size];
        // 12ms
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = size - 1; i >= 0; i--) {
            while (!deque.isEmpty() && deque.peek() <= list.get(i)) {
                deque.pop();
            }
            if (!deque.isEmpty()) {
                ans[i] = deque.peek();
            }
            deque.push(list.get(i));
        }
        // 1102ms
//        for (int i = 0; i < size; i++) {
//            if (i > 0 && list.get(i) > list.get(i - 1) && (ans[i - 1] > list.get(i) || ans[i - 1] == 0)) {
//                ans[i] = ans[i - 1];
//            } else {
//                for (int j = i + 1; j < size; j++) {
//                    if (list.get(j) > list.get(i)) {
//                        ans[i] = list.get(j);
//                        break;
//                    }
//                }
//            }
//        }
        return ans;
    }
}

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

